from collections import deque
from typing import List, Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def generate_binary_tree(root: List[Optional[int]]) -> Optional[TreeNode]:
    if not root or root[0] is None:
        return None

    # 创建根节点
    tree_root = TreeNode(root[0])
    queue = deque([tree_root])
    i = 1  # 数组指针，从第二个元素开始

    while queue and i < len(root):
        node = queue.popleft()

        # 构建左子节点
        if i < len(root) and root[i] is not None:
            node.left = TreeNode(root[i])
            queue.append(node.left)
        i += 1

        # 构建右子节点
        if i < len(root) and root[i] is not None:
            node.right = TreeNode(root[i])
            queue.append(node.right)
        i += 1

    return tree_root


# 简单的层序遍历打印二叉树结构（仅打印节点值）
def print_tree(root: Optional[TreeNode]):
    if not root:
        return
    queue = deque([root])
    result = []
    while queue:
        node = queue.popleft()
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    print(result)


def bfs_level_order(root):
    if not root:
        return []

    result = []
    queue = deque([root])  # 初始化队列

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()  # 从左侧出队
            level.append(node.val)

            if node.left:
                queue.append(node.left)  # 加入左子节点
            if node.right:
                queue.append(node.right)  # 加入右子节点

        result.append(level)

    return result


def maxSlidingWindow(nums, k):
    result = []
    dq = deque()  # 保存的是下标，不是值

    for i in range(len(nums)):
        # 如果队头元素不在滑动窗口内，弹出
        if dq and dq[0] <= i - k:
            dq.popleft()

        # 保证队列中从头到尾是递减的，队尾不满足的都要弹出
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()

        dq.append(i)

        # 从第 k-1 个元素开始收集答案
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


# 示例测试
if __name__ == "__main__":
    root_list = [3, 2, 3, None, 3, None, 1]
    tree = generate_binary_tree(root_list)
    print_tree(tree)

    print("--------------------------------")

    # 测试
    root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
    print(bfs_level_order(root))  # 输出：[[1], [2, 3], [4, 5]]

    print("--------------------------------")

    # 测试
    nums = [1, 3, -1, -3, 5, 3, 6, 7]
    k = 3
    print(maxSlidingWindow(nums, k))  # 输出：[3, 3, 5, 5, 6, 7]

    print("--------------------------------")
